﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Common.Aho
{
    public class TireTree
    {
        public TireTree(char? value=null,TireTree parentNode=null,bool isRoot=false) 
        { 
            Value = value;
            ParentNode = parentNode;
            this.isRoot = isRoot;
        }
        public char? Value { get; set; }
        public TireTree ParentNode { get; set; }
        public Dictionary<char, TireTree> NextNodes { get; set; } = new Dictionary<char, TireTree>();
        public TireTree FailureNode { get; set; }
        public List<int> OutPuts { get; set; } = new List<int>();
        public bool IgnoreCase { get; set; }
        private bool isEnd;
        private bool isBuild = false;
        private bool isRoot = false;
        /// <summary>
        /// 插入关键字 
        /// </summary>
        /// <param name="keywords"></param>
        public void Insert(IEnumerable<string> keywords)
        {
            foreach(string keyword in keywords)
            {
                Insert(keyword);
            }
        }
        /// <summary>
        /// 插入关键字
        /// </summary>
        /// <param name="keywords"></param>
        public void Insert(params string[] keywords)
        {
            foreach(var keyword in keywords)
            {
                Insert(keyword);
            }
        }
        /// <summary>
        /// 插入关键字
        /// </summary>
        /// <param name="keyword"></param>
        public void Insert(string keyword)
        {
            if (string.IsNullOrWhiteSpace(keyword)) return;
            isBuild = false;
            TireTree parentNode = this;
            for(int i = 0; i < keyword.Length; i++)
            {
                char key=IgnoreCase?keyword.ToUpper()[i]: keyword[i];
                if (!parentNode.NextNodes.TryGetValue(key, out TireTree node))
                {
                    node=new TireTree(key,parentNode);
                    parentNode.NextNodes.Add(key, node);
                }
                parentNode = node;
                if(i== keyword.Length - 1)
                {
                    node.isEnd = true;
                    node.OutPuts.Add(keyword.Length);
                }
            }
        }

        //public void Remove(string keyword)
        //{
        //    isBuild = false;
        //    List<TireTree> tireTrees = GetTireTree(keyword);
        //    foreach(var tireTree in tireTrees)
        //    {
        //        tireTree.OutPuts.Remove(keyword.Length);
        //    }
        //}
        public List<string> Search(string word)
        {
            if (!isRoot) throw new ArgumentException("the first node must be root!");
            List<TireTree> tireTrees = GetTireTree(IgnoreCase?word.ToUpper():word);
            List<string> keywords = new List<string>();
            foreach(TireTree tire in tireTrees)
            {
                keywords.AddRange(GetAllKeyword(tire));
            }
            return keywords;
        }
        private List<TireTree> GetTireTree(string keyword)
        {
            if (!isBuild)
            {
                CreateFailure();
                isBuild = true;
            }
            List<TireTree> tireTrees = new List<TireTree>();
            TireTree root = this;
            foreach (char key in keyword)
            {
                if (root.NextNodes.TryGetValue(key, out TireTree result))
                {
                    root = result;
                    if (result.isEnd)
                    {
                        tireTrees.Add(root);
                    }
                }
                else
                {
                    root = root.FailureNode;
                }
            }
            return tireTrees;
        }
        private List<string> GetAllKeyword(TireTree tiretree)
        {
            List<string> keywords = new List<string>();
            if (!tiretree.isEnd) throw new ArgumentException("node is not end!");
            foreach(int path in tiretree.OutPuts)
            {
                StringBuilder sb =new StringBuilder();
                TireTree current = tiretree;
                sb.Append(tiretree.Value);
                for (int i = 0; i < path-1; i++)
                {
                    current = current.ParentNode;
                    sb.Insert(0, current.Value);
                }
                keywords.Add(sb.ToString());
            }
            return keywords;
        }
        /// <summary>
        /// 建立failture表
        /// </summary>
        private void CreateFailure()
        {
            BFS(node =>
            {
                if (node.isRoot)
                {
                    node.FailureNode = node;
                }
                else
                {
                    TireTree parentNode = node.ParentNode;
                    if (parentNode.isRoot)
                    {
                        node.FailureNode = node.ParentNode;
                    }
                    else
                    {
                        TireTree failureNode = parentNode;
                        while (!failureNode.isRoot)
                        {
                            failureNode = failureNode.ParentNode;
                        }
                        if (parentNode.ParentNode.NextNodes.TryGetValue(node.Value.Value, out TireTree sameNode))
                        {
                            failureNode = sameNode;
                        }
                        else if(parentNode.FailureNode.NextNodes.TryGetValue(node.Value.Value,out TireTree sameNode1))
                        {
                            failureNode = sameNode1;
                        }
                        node.FailureNode = failureNode;
                        if (failureNode.isEnd )
                        {
                            node.OutPuts.AddRange(failureNode.OutPuts);
                        }
                    }
                }
            });
        }
        /// <summary>
        /// bfs遍历整个tire树
        /// </summary>
        /// <param name="action"></param>
        public void BFS(Action<TireTree> action)
        {
            Queue<TireTree> quene=new Queue<TireTree>();
            quene.Enqueue(this);
            while (quene.Count > 0)
            {
                TireTree tireTree = quene.Dequeue();
                action.Invoke(tireTree);
                foreach (TireTree children in tireTree.NextNodes.Values)
                {
                    quene.Enqueue(children); 
                }
            }
        }
    }
}
